import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
class ListNode{
    ListNode next;
    int val;
    ListNode(int x) {
        val = x;
         next = null;
    }
}

/**
 * BM5 合并k个已排序的链表
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        ListNode head = null;//最终返回的头节点
        ListNode cur = null;
        //1.先把数组中每个链表的头节点存入堆中->建立小根堆
        for(int i = 0;i<lists.size();i++){
            if(lists.get(i) != null)
                heap.offer(lists.get(i));
        }
        while(heap.size() > 0){
            //取出堆头 -最小值
            ListNode top = heap.poll();
            //因为head没有赋值，第一次先给head
            if(head == null){
                head = top;
                cur = head;
            }else{
                cur.next = top;
                cur = cur.next;
            }
            //入堆，放入一个值 将取出的最小值下一个元素放进去
            if(top.next != null){
                heap.offer(top.next);
            }

        }
        return head;
    }
}